package com.wayne.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class Solution496 {
  public static int[] nextGreaterElement1(int[] nums1, int[] nums2) {
    int m = nums1.length, n = nums2.length;
    int[] res = new int[m];
    for (int i = 0; i < m; i++) {
      int j = 0;
      // 获取在nums2 的位置
      while (j < n && nums2[j] != nums1[i]) {
        j++;
      }
      int k = j + 1;
      while (k < n && nums2[k] < nums2[j]) {
        k++;
      }
      res[i] = k < n ? nums2[k] : -1;
    }
    return res;
  }

  public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int m =nums1.length, n = nums2.length;
    Deque<Integer> stack = new ArrayDeque<Integer>();
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = n - 1; i >= 0; --i) {
      int num = nums2[i];
      while (!stack.isEmpty() && num > stack.peek()) {
        stack.pop();
      }
      map.put(num, stack.isEmpty() ? -1 : stack.peek());
      stack.push(num);
    }
    int[] res = new int[m];
    for (int i=0;i<m;i++) {
      res[i] = map.get(nums1[i]);
    }
    return res;
  }


  public static void main(String[] args) {
    int[] nums1 = new int[]{4, 1, 2}, nums2 = new int[]{3, 1, 4, 2};
    System.out.println(nextGreaterElement(nums1, nums2));
  }
}